#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>
#include "hashtbl.h"

struct bucket {
	void *key;
	void *val;
	struct bucket *next;
};

struct hash_table {
	struct bucket **table;
	int tab_sz;
	int num_elem;

	htab_hash_func_t hash;
	htab_cmp_func_t cmp;
};

static struct bucket *get_bucket(struct hash_table *htab, void *key);
static int rehash(struct hash_table *htab, int newsz);
static int next_prime(int p);

struct hash_table *htab_create(htab_hash_func_t hash, htab_cmp_func_t cmp)
{
	struct hash_table *htab;

	if(!(htab = malloc(sizeof *htab))) {
		return 0;
	}
	htab->table = 0;
	htab->tab_sz = 0;
	htab->num_elem = 0;
	htab->hash = hash;
	htab->cmp = cmp;

	if(rehash(htab, 101) == -1) {
		free(htab);
		return 0;
	}
	return htab;
}

void htab_free(struct hash_table *htab)
{
	int i;

	if(!htab) return;

	for(i=0; i<htab->tab_sz; i++) {
		struct bucket *iter = htab->table[i];

		while(iter) {
			void *tmp = iter;
			iter = iter->next;
			free(tmp);
		}
	}
	free(htab->table);
	free(htab);
}

int htab_add(struct hash_table *htab, void *key, void *value)
{
	unsigned int idx;
	struct bucket *bucket;

	if((bucket = get_bucket(htab, key))) {
		bucket->val = value;
		return 0;
	}

	if(!(bucket = malloc(sizeof *bucket))) {
		perror("failed to allocate bucket");
		return -1;
	}
	bucket->key = key;
	bucket->val = value;

	if(htab->tab_sz < htab->num_elem * 2) {
		if(rehash(htab, next_prime(htab->tab_sz * 2)) == -1) {
			perror("rehash failed");
			free(bucket);
			return -1;
		}
	}

	idx = htab->hash(key, htab->tab_sz);
	bucket->next = htab->table[idx];
	htab->table[idx] = bucket;
	htab->num_elem++;
	return 0;
}

int htab_del(struct hash_table *htab, void *key)
{
	unsigned int idx;
	struct bucket *iter;

	idx = htab->hash(key, htab->tab_sz);
	iter = htab->table[idx];

	if(htab->cmp(iter->key, key)) {
		htab->table[idx] = iter->next;
		free(iter);
		htab->num_elem--;
		return 0;
	}

	while(iter->next) {
		if(htab->cmp(iter->next->key, key)) {
			void *tmp = iter->next;
			iter->next = iter->next->next;
			free(tmp);
			htab->num_elem--;
			return 0;
		}
		iter = iter->next;
	}
	return -1;
}

void *htab_get(struct hash_table *htab, void *key)
{
	struct bucket *bucket = get_bucket(htab, key);
	return bucket ? bucket->val : 0;
}

unsigned int htab_hash_int(void *key, int sz)
{
	return *(int*)key % sz;
}

int htab_cmp_int(void *a, void *b)
{
	return *(int*)a == *(int*)b;
}

unsigned int htab_hash_string(void *key, int sz)
{
	int hash = 0;
	int a = 31415;
	int b = 27183;
	char *sptr = key;

	while(*sptr) {
		hash = (a * hash + *sptr++) % sz;
		a = a * b % (sz - 1);
	}
	return hash < 0 ? hash + sz : hash;
}

int htab_cmp_string(void *a, void *b)
{
	return strcmp(a, b) == 0;
}



static struct bucket *get_bucket(struct hash_table *htab, void *key)
{
	int idx;
	struct bucket *iter;

	idx = htab->hash(key, htab->tab_sz);
	iter = htab->table[idx];

	while(iter) {
		if(htab->cmp(iter->key, key)) {
			break;
		}
		iter = iter->next;
	}
	return iter;
}

static int rehash(struct hash_table *htab, int newsz)
{
	int i;
	struct hash_table new_ht;

	new_ht.tab_sz = newsz;
	new_ht.num_elem = 0;
	new_ht.hash = htab->hash;
	new_ht.cmp = htab->cmp;

	if(!(new_ht.table = malloc(newsz * sizeof *new_ht.table))) {
		return -1;
	}
	memset(new_ht.table, 0, newsz * sizeof *new_ht.table);

	for(i=0; i<htab->tab_sz; i++) {
		struct bucket *iter = htab->table[i];

		while(iter) {
			void *tmp = iter;
			htab_add(&new_ht, iter->key, iter->val);
			iter = iter->next;
			free(tmp);
		}
	}

	free(htab->table);
	htab->table = new_ht.table;
	htab->tab_sz = newsz;
	return 0;
}

static int is_prime(int num)
{
	int i, sqrt_num;

	if(num < 2) return 0;
	if(num != 2 && num % 2 == 0) {
		return 0;
	}

	sqrt_num = (int)sqrt(num);
	for(i=3; i<=sqrt_num; i++) {
		if(num % i == 0) {
			return 0;
		}
	}
	return 1;
}

static int next_prime(int p)
{
	while(p < INT_MAX && !is_prime(p)) {
		p++;
	}
	return p;
}
